package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/design-front-middle-back-queue/'>找出临界点之间的最小和最大距离(Find the Minimum and Maximum Number of Nodes Between Critical Points)</a>
 * <p>链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点 。</p>
 * <p>如果当前节点的值 严格大于 前一个节点和后一个节点，那么这个节点就是一个  局部极大值点 。</p>
 * <p>如果当前节点的值 严格小于 前一个节点和后一个节点，那么这个节点就是一个  局部极小值点 。</p>
 * <p>注意：节点只有在同时存在前一个节点和后一个节点的情况下，才能成为一个 局部极大值点 / 极小值点 。</p>
 * <p>给你一个链表 head ，返回一个长度为 2 的数组 [minDistance, maxDistance] ，其中 minDistance 是任意两个不同临界点之间的最小距离，maxDistance 是任意两个不同临界点之间的最大距离。如果临界点少于两个，则返回 [-1，-1] 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [3,1]
 *      输出：[-1,-1]
 *      解释：链表 [3,1] 中不存在临界点。
 *
 * 示例 2：
 *      输入：head = [5,3,1,2,5,1,2]
 *      输出：[1,3]
 *      解释：存在三个临界点：
 *          - [5,3,1,2,5,1,2]：第三个节点是一个局部极小值点，因为 1 比 3 和 2 小。
 *          - [5,3,1,2,5,1,2]：第五个节点是一个局部极大值点，因为 5 比 2 和 1 大。
 *          - [5,3,1,2,5,1,2]：第六个节点是一个局部极小值点，因为 1 比 5 和 2 小。
 *          第五个节点和第六个节点之间距离最小。minDistance = 6 - 5 = 1 。
 *          第三个节点和第六个节点之间距离最大。maxDistance = 6 - 3 = 3 。
 *
 * 示例 3：
 *      输入：head = [1,3,2,2,3,2,2,2,7]
 *      输出：[3,3]
 *      解释：存在两个临界点：
 *          - [1,3,2,2,3,2,2,2,7]：第二个节点是一个局部极大值点，因为 3 比 1 和 2 大。
 *          - [1,3,2,2,3,2,2,2,7]：第五个节点是一个局部极大值点，因为 3 比 2 和 2 大。
 *          最小和最大距离都存在于第二个节点和第五个节点之间。
 *          因此，minDistance 和 maxDistance 是 5 - 2 = 3 。
 *          注意，最后一个节点不算一个局部极大值点，因为它之后就没有节点了。
 *
 * 示例 4：
 *      输入：head = [2,3,3,2]
 *      输出：[-1,-1]
 *      解释：链表 [2,3,3,2] 中不存在临界点。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>链表中节点的数量在范围 [2, 10^5] 内</li>
 *      <li>1 <= Node.val <= 10^5</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/11 13:54
 */
public class LC2058FindMinimumAndMaximumNumberOfNodesBetweenCriticalPoints_M {
    static class Solution {
        public int[] nodesBetweenCriticalPoints(ListNode head) {
            int minDistance = Integer.MAX_VALUE;
            // 第一个临界值的位置
            int firstCriticalPointIndex = -1;
            // 上一个临界值的位置
            int prevCriticalPointsIndex = -1;

            int prevNodeVal = head.val;
            head = head.next;
            for (int currIndex = 2; head.next != null; currIndex++, head = head.next) {
                // 临界点
                if ((head.val > head.next.val && head.val > prevNodeVal) || (head.val < head.next.val && head.val < prevNodeVal)) {
                    // 只找到第一个临界点时，是不需要更新最大值和最小值的。当找到两个及以上的临界点时，才需要更新
                    if (firstCriticalPointIndex == -1) {
                        firstCriticalPointIndex = currIndex;
                    } else {
                        minDistance = Math.min(minDistance, currIndex - prevCriticalPointsIndex);
                    }
                    //System.out.println("第"+currIndex+"节点是一个临界值");
                    prevCriticalPointsIndex = currIndex;
                }

                prevNodeVal = head.val;
            }
            if (firstCriticalPointIndex == prevCriticalPointsIndex) {
                return new int[]{-1, -1};
            } else {
                return new int[]{minDistance, prevCriticalPointsIndex - firstCriticalPointIndex};
            }
        }

        public int[] nodesBetweenCriticalPoints2(ListNode head) {
            int minDistance = Integer.MAX_VALUE;
            // 第一个临界值的位置
            int firstCriticalPointIndex = -1;
            // 上一个临界值的位置
            int prevCriticalPointsIndex = -1;

            ListNode prevNode = head;
            ListNode currNode = head.next;
            ListNode nextNode = head.next.next;

            for (int currIndex = 2; nextNode != null; currIndex++) {
                // 临界点
                if ((currNode.val > prevNode.val && currNode.val > nextNode.val) || (currNode.val < prevNode.val && currNode.val < nextNode.val)) {
                    // 只找到第一个临界点时，是不需要更新最大值和最小值的。当找到两个及以上的临界点时，才需要更新
                    if (firstCriticalPointIndex == -1) {
                        firstCriticalPointIndex = currIndex;
                    } else {
                        minDistance = Math.min(minDistance, currIndex - prevCriticalPointsIndex);
                    }
                    //System.out.println("第"+currIndex+"节点是一个临界值");
                    prevCriticalPointsIndex = currIndex;
                }
                prevNode = currNode;
                currNode = nextNode;
                nextNode = nextNode.next;
            }
            if (firstCriticalPointIndex == prevCriticalPointsIndex) {
                return new int[]{-1, -1};
            } else {
                return new int[]{minDistance, prevCriticalPointsIndex - firstCriticalPointIndex};
            }
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(3);
        head1.next = new ListNode(1);

        ListNode head2 = new ListNode(5);
        head2.next = new ListNode(3);
        head2.next.next = new ListNode(1);
        head2.next.next.next = new ListNode(2);
        head2.next.next.next.next = new ListNode(5);
        head2.next.next.next.next.next = new ListNode(1);
        head2.next.next.next.next.next.next = new ListNode(2);

        ListNode head3 = new ListNode(1);
        head3.next = new ListNode(3);
        head3.next.next = new ListNode(2);
        head3.next.next.next = new ListNode(2);
        head3.next.next.next.next = new ListNode(3);
        head3.next.next.next.next.next = new ListNode(2);
        head3.next.next.next.next.next.next = new ListNode(2);
        head3.next.next.next.next.next.next.next = new ListNode(2);
        head3.next.next.next.next.next.next.next.next = new ListNode(7);

        Solution solution = new Solution();
        Printer.printArrayInt(solution.nodesBetweenCriticalPoints2(head1));
        Printer.printArrayInt(solution.nodesBetweenCriticalPoints2(head2));
        Printer.printArrayInt(solution.nodesBetweenCriticalPoints2(head3));
    }
}
